package arithmetic2.day03;

import java.util.Arrays;

/*
    优化基数排序
 */
public class Demo04 {
    public static void main(String[] args) {
//        int arr[] = new int[]{102, 12, 4, 1235, 1001};
        int arr[] = new int[100];
        for(int i=0;i<arr.length;i++){
            arr[i] = (int)(Math.random()*100);
        }
        radixSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    //基数排序
    public static void radixSort(int arr[], int start, int end) {
        //找到数组中最大的数，求出数的长度
        int max = max(arr);
        int digit = (max + "").length();
        //将数组基数排序
        radix(arr, start, end, digit);
    }

    //进桶出桶过程   123  个位数=(123/10^0)%10 十位数=(123/10^1)%10 百位数=(123/10^2)%10
    public static void radix(int arr[], int start, int end, int digit) {
        //辅助数组
        int temp[] = new int[end - start + 1];
        //总共有digit次过程
        for (int i = 0; i < digit; i++) {
            //定义词频统计表,统计某个位上为i的数的个数(个位，十位，百位)
            int count[] = new int[10];
            //遍历数组,得到词频统计表
            for (int j = start; j <= end; j++) {
                //统计某个位上的数
                count[(arr[j] / (int) Math.pow(10, i)) % 10]++;
            }
            //将词频统计表变为前缀和表
            for (int j = 0; j < count.length; j++) {
                if (j >= 1) {
                    count[j] += count[j - 1];
                }
            }
            //从右往左遍历原数组，将数按照某种规则加到辅助数组中
            for (int j = end; j >= start; j--) {
                //这个数的某个位索引到count中，count[i]-1为在放入temp中的位置，然后对应的词频-1
                //得到这个数某个位的值
                int index = (arr[j] / (int) Math.pow(10, i)) % 10;
                //将这个数放在count[index]-1的位置
                temp[count[index] - 1] = arr[j];
                //count[index]-1
                count[index]--;
//                temp[count[(arr[j]/(int)Math.pow(10,i)) % 10] - 1] = arr[j];
            }
            //将temp中的数赋值给原数组
            for (int j = start; j <= end; j++) {
                arr[j] = temp[j];
            }
        }
    }

    //得到数组中最大的数
    public static int max(int arr[]) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        return max;
    }
}
